package com.cdy.demo.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 226. 翻转二叉树
 * https://leetcode-cn.com/problems/invert-binary-tree/
 */
public class ChangeTree {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        change(root, root.left, root.right);
        return root;
    }

    public void change(TreeNode parent, TreeNode left, TreeNode right) {
        if (parent == null) {
            return;
        }
        if (left != null) {
            change(left, left.left, left.right);
        }
        if (right != null) {
            change(right, right.left, right.right);
        }
        parent.left = right;
        parent.right = left;

    }

//二叉树的所有路径
    //https://leetcode-cn.com/problems/binary-tree-paths/
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<String>();
        if (root.left != null){
            binaryTreePaths(list, root.val+"", root.left);
        }
        if (root.right != null) {
            binaryTreePaths(list, root.val+"", root.right);
        }
        if (root.left == null && root.right == null) {
            list.add(root.val + "");
        }

        return list;
    }

    public void binaryTreePaths(List<String> list, String string, TreeNode node) {
        String tmp = string + "->" + node.val;
        if (node.left != null) {
            binaryTreePaths(list, tmp, node.left);
        }

        if (node.right != null) {
            binaryTreePaths(list, tmp, node.right);
        }

        if (node.left == null && node.right == null) {
            list.add(tmp);
        }
    }
}
